package com.faiz.algorithm;

import java.util.HashMap;
import java.util.Map;

public class LRUCache2 {

    private final DoubleList cache;
    private final Map<Integer, Node> map;
    private final int cap;

    public LRUCache2(int capacity) {
        cache = new DoubleList();
        map = new HashMap<>();
        cap = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        makeRecently(key);
        Node node = map.get(key);
        return node.val;
    }

    public void put(int key, int val) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = val;
            makeRecently(key);
            return;
        }

        if (cache.size == cap) {
            removeLeastRecently();
        }

        addRecently(key, val);
    }

    private void addRecently(int key, int val) {
        Node node = cache.addLast(key, val);
        map.put(key, node);
    }

    // 将当前缓存值设置为最近使用
    private void makeRecently(int key) {
        Node node = map.get(key);
        cache.remove(node);
        Node newNode = cache.addLast(key, node.val);
        map.put(key, newNode);
    }

    // 移除当前最少使用的缓存
    private void removeLeastRecently() {
        int key = cache.removeFirst();
        map.remove(key);
    }


    static class DoubleList {
        private final Node head;
        private Node tail;
        private int size;

        public DoubleList() {
            head = new Node(-1, -1);
            tail = head;
            size = 0;
        }

        // 定义： 接近尾部的是最近使用的，接近头部的即将进行淘汰的
        // 向尾部添加节点
        public Node addLast(int key, int val) {
            Node node = new Node(key, val);
            tail.next = node;
            node.pre = tail;
            tail = node;
            size++;
            return node;
        }

        // 移除节点
        public void remove(Node node) {
            Node pre = node.pre;
            // 这里需要确保node.next不为空
            Node next = node.next;
            pre.next = next;
            node.next = null;
            node.pre = null;
            if (next == null) {
                tail = pre;
            } else {
                next.pre = pre;
            }
            size--;
        }

        // 移除最近没有使用的节点
        public int removeFirst() {
            Node node = head.next;
            remove(node);
            return node.key;
        }
    }

    static class Node {
        Node pre;
        Node next;
        int key;
        int val;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public static void main(String[] args) {
        LRUCache2 lru = new LRUCache2(2);
        lru.put(2, 1);
        lru.put(2, 2);
        int v1 = lru.get(2);
        lru.put(1, 1);
        lru.put(4, 1);
        lru.get(2);
    }
}
